package Q654;

/**
 * 最大二叉树
 *
 * @author 23737
 * @time 2021.12.11
 */
public class Test {
    public static void main(String[] args) {

    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 递归解法
 * 分成左右两个子树分别构造
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        int len = nums.length;
        ;
        return constructMaximumBinaryTree(nums, 0, len);
    }

    public TreeNode constructMaximumBinaryTree(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {
            return null;
        }
        if (rightIndex - leftIndex == 1) {
            return new TreeNode(nums[leftIndex]);
        }
        int maxVal = nums[leftIndex];
        int maxIndex = leftIndex;
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal) {
                maxIndex = i;
                maxVal = nums[i];
            }
        }
        TreeNode treeNode = new TreeNode(maxVal);
        treeNode.left = constructMaximumBinaryTree(nums, leftIndex, maxIndex);
        treeNode.right = constructMaximumBinaryTree(nums, maxIndex + 1, rightIndex);
        return treeNode;
    }
}
